Validate stack sequences [Greedy]

Time: O(N); Space: O(N); medium

Given two sequences pushed and popped with distinct values, return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.

Example 1:

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]

Output: True

Explanation:

  • We might do the following sequence:

  • push(1), push(2), push(3), push(4), pop() -> 4,

  • push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Example 2:

Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]

Output: False

Explanation:

  • 1 cannot be popped before 2.

Constraints:

  1. 0 <= pushed.length == popped.length <= 1000

  2. 0 <= pushed[i], popped[i] < 1000

  3. pushed is a permutation of popped.

  4. pushed and popped have distinct values.

1. Greedy

Intuition

We have to push the items in order, so when do we pop them?

If the stack has say, 2 at the top, then if we have to pop that value next, we must do it now. That’s because any subsequent push will make the top of the stack different from 2, and we will never be able to pop again.

Algorithm

For each value, push it to the stack.

Then, greedily pop values from the stack if they are the next values to pop.

At the end, we check if we have popped all the values successfully.

[14]:

class Solution1(object):
    """
    Time:  O(N), where N is the length of pushed and popped.
    Space: O(N)
    """
    def validateStackSequences(self, pushed, popped):
        """
        :type pushed: List[int]
        :type popped: List[int]
        :rtype: bool
        """
        i = 0
        s = []
        for v in pushed:
            s.append(v)
            while s and i < len(popped) and s[-1] == popped[i]:
                s.pop()
                i += 1
        return i == len(popped)


[15]:

s = Solution1()
pushed = [1,2,3,4,5]
popped = [4,5,3,2,1]
assert s.validateStackSequences(pushed, popped) == True
pushed = [1,2,3,4,5]
popped = [4,3,5,1,2]
assert s.validateStackSequences(pushed, popped) == False